/**
 * @file   Hash.h
 * @author xingyifan <xingyifan@xingyifan-VirtualBox>
 * @date   Sat Dec 12 10:17:33 2020
 * 
 * @brief  Hash declare
 * 
 * 
 */

#ifndef __HASH__LIST__
#define __HASH__LIST__

#include <iostream>
#define LENGTH 400
#define length 20

class Hash {
private:    
    class Node {
    public:
	char s[length];
	int count;
	Node * next;
	Node() {
	    count = 0;
	    s[0] = '0'; //to compare with new words
	    Node * next = NULL;
	};
    };
    int collision;   //record the max collision time
    void insert(Node * tmp, char _s[]);    //insert words in tmp
    void clear(Node * _x); //delete the node list
    int hashing(char * _s); //hashing map
    int compare(char x[], char y[]); //compare if _x == _y
    void sep(char * _s); //delete the useless sign
public:
    Node * list[LENGTH];
    Hash() {
	for (int i=0;i<LENGTH;i++) {
	    list[i] = new Node;
	}
	collision = 0;
    };
    int max_collision();    //return collision time
    int counting(char _s[]); //counting the number of _s
    void Insert(char _s[]); //Insert new words
    void print(); //print the whole list
    void max(); //print the 20 words
    ~Hash();
};

/**
 * @file   Hash.h
 * @author xingyifan <xingyifan@xingyifan-VirtualBox>
 * @date   Sat Dec 12 11:00:11 2020
 * 
 * @brief  hashing map
 * 
 * 
 */

int Hash::hashing(char * _s) {
    int x = 0;
    int multiple = 1;
    for (int i=0;_s[i]!=0;i++) {
	x += (_s[i] - 'a') << multiple;
	multiple++;
    }

    return x%397;
}

/**
 * @file   Hash.h
 * @author xingyifan <xingyifan@xingyifan-VirtualBox>
 * @date   Sat Dec 12 11:00:32 2020
 * 
 * @brief  record data
 * 
 * 
 */

int Hash::max_collision() {
    return collision;
}

int Hash::counting(char _s[]) {
    int index = hashing(_s);
    Node * tmp = list[index];
    while (tmp->next!=NULL && compare(tmp->s, _s)==0) {
	tmp = tmp->next;
    }

    if (tmp->count) {
	std::cout << tmp->s << " ";
    }
	
    return tmp->count;
}

/**
 * @file   Hash.h
 * @author xingyifan <xingyifan@xingyifan-VirtualBox>
 * @date   Sat Dec 12 10:59:58 2020
 * 
 * @brief  insert words
 * 
 * 
 */

void Hash::Insert(char _s[]) {
    char * p = _s;
    sep(p);
    if (_s[0]==0) {
	return;
    }
    int index = hashing(_s);
    Node * tmp = list[index];
    int check;
    int depth = 0;
    while ((check=compare(tmp->s, _s))==0) {
	if (tmp->next==NULL) {
	    tmp->next = new Node;
	    tmp->count++;
	    insert(tmp, _s);
	    break;
	}
	tmp = tmp->next;
	depth++;
    }
    if (check) {
	tmp->count++;
    }
    if (depth>collision) {
	collision = depth;
    }
}

void Hash::insert(Node * tmp, char _s[]) {
    int i;
    for (i=0;_s[i]!=0;i++) {
	tmp->s[i] = _s[i];
    }
    tmp->s[i] = 0;
}

/**
 * @file   Hash.h
 * @author xingyifan <xingyifan@xingyifan-VirtualBox>
 * @date   Sat Dec 12 10:59:37 2020
 * 
 * @brief  deal with the string
 * 
 * 
 */

int Hash::compare(char x[], char y[]) {
    for (int i=0;x[i]!=0;i++) {
	if (x[i]!=y[i]) {
	    return 0;
	}
    }
    return 1;
}

void Hash::sep(char * _s) {
    int index = 0;
    char s[length];
    for (int i=0;_s[i]!=0;i++) {
	if (_s[i]>='A' && _s[i]<='Z') {
	    s[index] = _s[i] + 32;	    
	} else if (_s[i]>='a' && _s[i]<='z') {
	    s[index] = _s[i];
	} else {
	    continue;
	}
	index++;
    }
    s[index] = 0;

    int i;
    for (i=0;s[i]!=0;i++) {
	_s[i] = s[i];
    }
    _s[i] = 0;
}

/**
 * @file   Hash.h
 * @author xingyifan <xingyifan@xingyifan-VirtualBox>
 * @date   Sat Dec 12 10:59:24 2020
 * 
 * @brief  show the list
 * 
 * 
 */

void Hash::print() {
    for (int i=0;i<LENGTH;i++) {
	if (list[i]->count>0) {
	    Node * tmp = list[i];
	    do {
		std::cout << tmp->s << ": " << tmp->count <<  std::endl;
		tmp = tmp->next;
	    } while (tmp->next!=NULL);
	}
    }
}

void Hash::max() {
    Node * maxl[length];
    for (int i=0;i<length;i++) {
	maxl[i] = new Node;
    }
    
    for (int i=0;i<LENGTH;i++) {
	if (list[i]->count>0) {
	    Node * tmp = list[i];
	    do {
		for (int i=0;i<length;i++) {
		    if (tmp->count>maxl[i]->count) {
			for (int j=length;j>i;j--) {
			    maxl[j] = maxl[j-1];
			}
			maxl[i] = tmp;
			break;
		    }
		}
		tmp = tmp->next;
	    } while (tmp->next!=NULL);
	}
    }

    for (int i=0;i<length;i++) {
	std::cout << maxl[i]->s << ": " << maxl[i]->count << std::endl;
	delete maxl[i];
    }
}

/**
 * @file   Hash.h
 * @author xingyifan <xingyifan@xingyifan-VirtualBox>
 * @date   Sat Dec 12 10:58:47 2020
 * 
 * @brief  delete the hash list
 * 
 * 
 */

Hash::~Hash() {
    for (int i=0;i<LENGTH;i++) {
	clear(list[i]);
    }
}

void Hash::clear(Node * _x) {
    Node * next = _x->next;

    if (next!=NULL) {
	clear(next);
    }

    delete(_x);
}

#else
//Do nothing
#endif
